#include<bits/stdc++.h>
using namespace std;
const int maxn = 1006;
int dp[maxn][maxn];
void pre() {
  for(int i=1; i<maxn; ++i) {
    for(int j=1; j<maxn; ++j) {
      dp[i][j] = max(dp[i-1][j], dp[i][j-1])+(__gcd(i,j)==1?1:0);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  pre();
  int tc; cin>>tc;
  while(tc--) {
    int a, b;
    cin>>a>>b;
    cout<<dp[a][b]<<'\n';
  }
}
